package primary.primary0;


import java.util.Deque;
import java.util.LinkedList;


/**
 * 单调栈，动态规划
 */
public class S0739每日温度 {


    /**
     * 45, 14
     * 单调栈
     * 要通过栈来同时维护两个信息 1. 元素的大小 2. 元素在入参中的序号
     * 这个很困难，需要栈元素为新的类。所以栈中放的都只是序号，栈的大小比较通过 temperatures[栈序号]来相互比较。
     * 相当于吧temperature来当成根据地址找大小的map
     */
    public int[] dailyTemperatures3(int[] temperatures) {
        int totalLen = temperatures.length;
        int[] res = new int[totalLen];
        // 通俗地理解一下，从前往后扫描每一个数，当前数值t[i]，会把前面每一个比他小的数，res[j]都改成 i - j
        // 但是res里的每一个元素，只会被改第一次。也就是被改了之后，就丢掉了。
        Deque<Integer> stack = new LinkedList<>();

        for(int i = 0; i < totalLen; i++){
            if(stack.isEmpty()){
                stack.push(i);
            }else{
                if(temperatures[i] <= temperatures[stack.peek()]){
                    stack.push(i);
                }else {
                    while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
                        Integer location = stack.pop();
                        res[location] = i - location;
                    }
                    stack.push(i);
                }
            }
        }


        return res;
    }

    /**
     * 99, 97
     * 动态规划，从讨论区得到的方法，自己实现一下
     */
    public int[] dailyTemperatures2(int[] temperatures) {
        int totalLen = temperatures.length;
        int[] res = new int[totalLen];
        res[totalLen - 1] = 0;
        for(int i = totalLen - 2; i >= 0; i--){
            if(temperatures[i] < temperatures[i + 1]){
                res[i] = 1;
            }else if(temperatures[i] == temperatures[i + 1]){
                // 注意这里 == 0 的逻辑，都是要单独判断的。
                if (res[i + 1] == 0) {
                    res[i] = 0;
                }else{
                    res[i] = res[i + 1] + 1;
                }

            }else{
                // 像跳表一样，逐个去找下一个比自己大的节点
                for(int j = i + 1; j < totalLen;){
                    if(temperatures[i] < temperatures[j]){
                        res[i] = j - i;
                        break;
                    }
                    if(res[j] == 0){
                        res[i] = 0;
                        break;
                    }
                    j += res[j];
                }
            }
        }
        return res;
    }


    /**
     * 先暴力试一下，最复杂的情况下是O(n^2)
     * 47 / 48时，时间超限
     */
    public int[] dailyTemperatures(int[] temperatures) {
        int totalLen = temperatures.length;
        int[] res = new int[totalLen];
        for(int i = 0; i < totalLen; i++){
            int base = temperatures[i];
            for(int j = i + 1; j < totalLen; j++){
                if(temperatures[j] > base){
                    res[i] = j - i;
                    break;
                }
            }
        }

        return res;
    }



}
